package com.AC.ACYuanFuDao;

import org.junit.Test;

public class test2 {

    public int maximalRectangle(int[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int n = matrix.length;
        int m = matrix[0].length;
        int res = 0;
        int[][] dp1 = new int[n][m+1];
        int[][] dp2 = new int[n][m+1];

        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                dp1[i][j] =  dp1[i > 0 ? i - 1 : 0 ][j] + matrix[i][j];
            }
        }

        for(int i = 0; i<n; i++){
            dp1[i][m] = dp1[i][0];
        }

        for(int i = 0; i<n; i++){
            for(int j = 1; j<=m; j++){
                dp2[i][j] =  dp2[i > 0 ? i - 1 : 0 ][j] + matrix[i][j-1];
            }
        }

        for(int i = 0; i<n; i++){
            dp2[i][0] = dp2[i][m];
        }



        for(int i = 0; i<n; i++){
            for(int j = 0; j<=m; j++){
                System.out.print(dp1[i][j] + " ");
            }
            System.out.println();
        }

        for(int i = 0; i<n; i++){
            for(int j = 0; j<=m; j++){
                System.out.print(dp2[i][j] + " ");
            }
            System.out.println();
        }





        return res;
    }

    public int findMaxRectangle(int[][] matrix){
        int n = matrix.length;
        int m = matrix[0].length;



        int max = 0;
        for(int i = 0; i<n; i++){
            int[] tmp = new int[m];
            for(int j = i; j<n; j++){
                int sum = 0;
                for(int k = 0; k<m; k++){
                    tmp[k] += matrix[j][k];
                    sum += tmp[k];
                    max = Math.max(max, sum);
                    sum = sum < 0 ? 0 : sum;
                }
            }
        }
        return max;
    }

    @Test
    public void test(){
        int[][] matrix1 = {
                {0,-2,-7,0},
                {9,2,-6,2},
                {-4,1,-4,1},
                {-1,8,0,-2}
        };
        int[][] matrix2 = {
                {2,3,0},
                {2,1,2},
                {3,-2,4}
        };
//        System.out.println(maximalRectangle(matrix2));
//        System.out.println(findMaxRectangle(new int[]{1,0}));
        System.out.println(findMaxRectangle(matrix1));
    }


}
